第八天 CPU Scheduling--上

今天我們來說說CPU的排程吧！先來講基本的排程概論：
CPU Scheduling是為了要讓CPU在多處理器的架構下，能有最好的運用效能。在執行時，CPU跟I/O burst會輪流執行，形成CPU-I/O Burst Cycle，在這兩者之中，CPU burst的分配是最主要的，而且短時間內CPU跟I/O互相作用(幾乎在10 milliseconds 內作用完成)。
而現在這裡講的CPU Scheduling是講short-term scheduling。CPU Scheduling是由short-term scheduler來負責。scheduling的時間點有4個：

1. Running -> waiting
2. Running -> ready
3. Waiting -> ready
4. Terminates

其中的一跟四在排程時，是不能中斷的，二跟三是可以中斷，但需要考慮到是否有shared data、是否在kernel mode，還有他們是不是真的能中斷。
在scheduling中，真正把process搬上搬下(context switch)，還有把CPU控制權交給scheduler所選的process，其實是dispatcher。Dispatcher做的事情有：

• 內容轉換(register、program counter)
• 轉換到user mode
• 把控制權交到原user program指定的地址繼續進行

而要怎麼確認scheduling呢？以下有一些標準可以評斷：

• CPU的使用效率(CPU utilization) —越高越好
• 單位時間內完成的工作量(throughput) —越多越好
• Process進入CPU到完成的時間(turnaround time) —越短越好
• Process被叫進ready queue到完成時，等了多久(waiting time) —越短越好
• 當有需求時，多久能給回覆(response time) —越短越好

接下來我們來說排程的演算法，有以下幾種：

1. FCFS — First Come First-Served
   先到的先處理，不管要用CPU多少時間。如果同樣三個process，到的順序不同的話，waiting的時間也會不一樣。這種會出現convoy effect的現象(執行時間短的在長的後面)，讓平均等待時間拉長。雖然公平，但時間上是有問題的。
2. SJF — Shortest-Job-First(exponential averaging)
   執行時間短的會先執行，所以平均等待時間一定是最好的。可以算是最佳樺的演算法，但是需要預估未來工作的長度，不然執行時間長的永遠都等不到執行。

那要預估就需要用到exponential averaging，以下是他的公式：

我們通常會將α設定為1/2
而這種演算法，如果執行到一半，有一個比剩下要執行時間還短的process來，這時候就要先去執行新來的process。以下是舉例即說明：


還有幾個演算法，我們明天繼續討論！